// a simple binary tree class
// (c) Yongjin Park, 2012
//     ypark28@jhu.edu

#include <algorithm>
#include <cmath>
#include <iostream>
#include <fstream>
#include <sstream>
#include <cstdlib>
#include <cassert>
#include <boost/ptr_container/ptr_vector.hpp>
#include <vector>

#ifndef BTREE_HH_
#define BTREE_HH_

size_t
num_nodes( size_t depth )
{
  return ( 1 << (depth+1) ) - 1;
}

size_t
num_leaves( size_t depth )
{
  return ( 1 << depth );
}

// To find trailing zeros efficiently
// (source http://graphics.stanford.edu/~seander/bithacks.html)
static const int MultiplyDeBruijnBitPosition[32] =
  {
    0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
    31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
  };

// fixed binary tree class
template<typename T>
class btree_t
{

private:

  // we use conventional binary heap-like tree
  // constant time easy access
  // internal index for tree nodes

  // **************** useful facts ****************
  // root index = 0 and a single root is depth=1
  // clearly depth > 1, otherwise useless
  // pa[i] = floor( (i-1)/2 )
  // l[i] = 2*i + 1
  // r[i] = 2*i + 2
  // ntot = 2^(depth+1) -1
  // nleaves = 2^depth
  // leaf index = [2^depth-1 .. 2^(1+depth)-1)
  // 0-based indexing

  int depth;         // depth of a tree
  int ntot;          // total number of tree nodes
  int leaf_offset;   // (1 << (depth-1)) - 1

  // For faster lookups of a LCA
  // we use in-order traversal index
  // LCA(x,y) could be done in O(1)

  std::vector<int> inorder2tree; // inorder idx -> tree idx
  std::vector<int> tree2inorder; // tree idx -> inorder idx

  std::vector< T > node_data_map;

  // Recursively build a inorder traversal
  void dfs_inorder_idx(int root, int& idx);

  int left_idx(int ii) const;
  int right_idx(int ii) const;
  int pa_idx(int ii) const;
  int leaf_internal_idx(int k) const;

  // find the number of trailing zeros in 32-bit v
  int count_zeros_right(int v) const;

  // Fast access of lowest common ancestor of leaf_x and leaf_y
  // implemetation of Moufatich (2008)
  // takes internal index of (x, y) in [ leaf_offset .. ntot )
  // outputs internal index in [ 0 .. num_internals() )
  int get_lca(int xi, int yi) const;

  // lca node idx
  int get_lca_idx(int leaf_x, int leaf_y) const;

public:
  explicit btree_t( const int depth, typename std::vector< T >& data_vec );
  virtual ~btree_t();

  // leaf_x, leaf_y in [0 .. #leaves)
  T& get_lca_node(int leaf_x, int leaf_y);

  // leaf node data
  T& get_leaf_node(int leaf);

  // n-th node
  T& get_nth_node(int n);

  // leaf_x, leaf_y in [0 .. #leaves)
  const T& get_lca_node(int leaf_x, int leaf_y) const;

  // leaf node data
  const T& get_leaf_node(int leaf) const;

  // n-th node
  const T& get_nth_node(int n) const;

  int num_leaves() const;
  int num_internals() const;
  int num_nodes() const;
  int get_depth() const;

public:
  // node iterator class
  struct node_iterator_t
  {
    int id;
    T& data;
    btree_t& tree;

    node_iterator_t(int _id, T& _nd, btree_t& _t) : id(_id), data(_nd), tree(_t) {}

    node_iterator_t( node_iterator_t& other ) : id(other.id), data(other.data), tree(other.tree) {}

    node_iterator_t&
    operator = ( const node_iterator_t& rhs )
    {
      id = rhs.id;
      data = rhs.data;
      tree = rhs.tree;
      return *this;
    }

    int leaf_idx() const { return (id - tree.leaf_offset); }
    bool is_leaf() const { return (leaf_idx()>= 0 && leaf_idx()<tree.num_leaves()); }
    bool has_pa() const { return id > 0 && tree.pa_idx(id) >= 0; }
    
    const int hash() const { return id; }

    node_iterator_t&
    get_pa()
    const
    {
#ifdef DEBUG
      assert( has_pa() );
#endif
      return tree.node_iterator_map.at( tree.pa_idx(id) );
    }

    node_iterator_t&
    get_left()
    const
    {
#ifdef DEBUG
      assert( !is_leaf() );
#endif
      return tree.node_iterator_map.at( tree.left_idx(id) );
    }

    node_iterator_t&
    get_right()
    const
    {
#ifdef DEBUG
      assert( !is_leaf() );
#endif
      return tree.node_iterator_map.at( tree.right_idx(id) );
    }

    friend class btree_t;
  };


public:
  friend class node_iterator_t;

  node_iterator_t& root_node_iterator();
  node_iterator_t& left_node_iterator(node_iterator_t& node);
  node_iterator_t& right_node_iterator(node_iterator_t& node);
  node_iterator_t& pa_node_iterator(node_iterator_t& node);

  // leaf_x, leaf_y in [0 .. #leaves)
  node_iterator_t& get_lca_node_iterator(int leaf_x, int leaf_y);

  // just n-th one
  node_iterator_t& get_nth_node_iterator(int n);

  // leaf node 
  node_iterator_t& get_leaf_node_iterator(int leaf);

private:
  // pre-generated map
  // node idx to node pointer 
  typename boost::ptr_vector< node_iterator_t > node_iterator_map;

};

////////////////////////////////////////////////////////////////
template<typename T>
btree_t<T>::btree_t(int _depth, typename std::vector<T>& dvec)
{
  depth = std::max(1,_depth); // depth should be at least 2

  ntot = (1 << (1+depth)) - 1;
  inorder2tree.resize(ntot,0);
  tree2inorder.resize(ntot,0);
  leaf_offset = (1 << depth) - 1;
  int idx = 0;                  // cumulative index
  dfs_inorder_idx(0,idx);         // build look-ups

#ifdef DEBUG
  assert( ntot == dvec.size() );
#endif

  for(int j=0; j<ntot;++j)
    {
      node_data_map.push_back( dvec.at(j) );
      node_iterator_map.push_back( new node_iterator_t(j, dvec.at(j), *this) );
    }
}

template<typename T>
btree_t<T>::~btree_t() {}



///////////////////////////////////////////////////////////////
// Recursively build a inorder traversal
template<typename T>
void
btree_t<T>::dfs_inorder_idx(int root, int& idx)			    
{
  int left = left_idx(root);
  int right = right_idx(root);
  if ( std::min(left,right) >= ntot )
    { // can't go further down
      inorder2tree[idx] = root;
      tree2inorder[root] = idx;
      ++idx;
      return;
    }
  dfs_inorder_idx(left,idx);
  inorder2tree[idx] = root;
  tree2inorder[root] = idx;
  ++idx;
  dfs_inorder_idx(right,idx);

  return;
}

template<typename T>
int
btree_t<T>::left_idx(int ii)
const
{
  return 2*ii+1;
}

template<typename T>
int
btree_t<T>::right_idx(int ii)
const
{
  return 2*ii+2;
}

template<typename T>
int
btree_t<T>::pa_idx(int ii)
const
{
  return (ii-1)/2;
}

template<typename T>
int
btree_t<T>::leaf_internal_idx(int k)
const
{
#ifdef DEBUG
  int ret = (k + leaf_offset);
  assert( k >= 0 && ret < ntot );
  return ret;
#else

  return (k + leaf_offset);
#endif

}

// find the number of trailing zeros in 32-bit v
template<typename T>
int
btree_t<T>::count_zeros_right(int v)
const
{
  int r;           // result goes here
  r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];
  return r;
}

// Fast access of lowest common ancestor of leaf_x and leaf_y
// implemetation of Moufatich (2008)
// takes internal index of (x, y) in [ leaf_offset .. ntot )
// outputs internal index in [ 0 .. num_internals() )
template<typename T>
int
btree_t<T>::get_lca(int xi, int yi)		    
const
{
#ifdef DEBUG
  assert( xi != yi );
#endif

  int x, y, idx1, idx2, idx3, idx, lca;
  x = tree2inorder[xi] + 1; // inorder index (1-based)
  y = tree2inorder[yi] + 1; // inorder index (1-based)

  int xy_xor = x ^ y;          // take difference of two bits
  idx1 = (int) log2(xy_xor);   // position of leftmost 1-bit
  idx2 = count_zeros_right(x); // #0's until rightmost 1-bit
  idx = std::max(idx1,idx2);   //
  idx3 = count_zeros_right(y); // #0's until rightmost 1-bit
  if( idx3 > idx )
    {
      lca = y;
    }
  else
    {
      lca = (x >> (idx+1)) << (idx+1);
    }
  lca = (lca | (1<<idx));

  return inorder2tree.at(lca-1);
}

// lca node idx
template<typename T>
int
btree_t<T>::get_lca_idx(int leaf_x, int leaf_y)
const
{
  if( leaf_x == leaf_y )
    return leaf_internal_idx( leaf_x );

  return get_lca( leaf_internal_idx(leaf_x), leaf_internal_idx(leaf_y) );
}


////////////////////////////////////////////////////////////////
// leaf_x, leaf_y in [0 .. #leaves)
template<typename T>
T&
btree_t<T>::get_lca_node(int leaf_x, int leaf_y)
{
  int lca = get_lca_idx( leaf_x, leaf_y );
  return node_data_map[lca];
}

// leaf node data
template<typename T>
T&
btree_t<T>::get_leaf_node(int leaf)
{
  return node_data_map[leaf_internal_idx(leaf)];
}

//
template<typename T>
T&
btree_t<T>::get_nth_node(int n)
{
#ifdef DEBUG
  assert( n >= 0 && n < ((int)ntot) );
#endif

  return node_data_map[n];
}

// leaf_x, leaf_y in [0 .. #leaves)
template<typename T>
const
T&
btree_t<T>::get_lca_node(int leaf_x, int leaf_y)
const
{
  //int lca = get_lca( leaf_internal_idx(leaf_x), leaf_internal_idx(leaf_y) );
  // tree_message( "has lca: " << lca << " of x=" << leaf_internal_idx(leaf_x) << " y=" << leaf_internal_idx(leaf_y) );
  int lca = get_lca_idx( leaf_x, leaf_y );
  return node_data_map.at(lca);
}

// leaf node data
template<typename T>
const
T&
btree_t<T>::get_leaf_node(int leaf)
const
{
  return node_data_map.at(leaf_internal_idx(leaf));
}

//
template<typename T>
const
T&
btree_t<T>::get_nth_node(int n)
const
{
#ifdef DEBUG
  assert( n >= 0 && n < ((int)ntot) );
#endif

  return node_data_map.at(n);
}

////////////////////////////////////////////////////////////////
template<typename T>
int
btree_t<T>::num_leaves()
const
{
  return (ntot - leaf_offset);
}

template<typename T>
int
btree_t<T>::num_internals()
const
{
  return leaf_offset;
}

template<typename T>
int
btree_t<T>::num_nodes()
const
{
#ifdef DEBUG
  assert( ntot == node_data_map.size() );
  assert( ntot == inorder2tree.size() );
  assert( ntot == tree2inorder.size() );
#endif

  return ntot;
}

template<typename T>
int
btree_t<T>::get_depth()
const
{
  return depth;
}

////////////////////////////////////////////////////////////////
template<typename T>
typename btree_t<T>::node_iterator_t&
btree_t<T>::root_node_iterator()
{
  return node_iterator_map[0];
}

template<typename T>
typename btree_t<T>::node_iterator_t&
btree_t<T>::left_node_iterator(node_iterator_t& node)
{
#ifdef DEBUG
  assert( !(node.is_leaf()) );
#endif

  int lid = left_idx(node.id);
  return node_iterator_map[lid];
}

template<typename T>
typename btree_t<T>::node_iterator_t&
btree_t<T>::right_node_iterator(node_iterator_t& node)
{
#ifdef DEBUG
  assert( !(node.is_leaf()) );
#endif

  int rid = right_idx(node.id);
  return node_iterator_map[rid];
}

template<typename T>
typename btree_t<T>::node_iterator_t&
btree_t<T>:: pa_node_iterator(node_iterator_t& node)
{
#ifdef DEBUG
  assert( node.has_pa() );
#endif

  int pa = pa_idx(node.id);
  return node_iterator_map[pa];
}


// leaf_x, leaf_y in [0 .. #leaves)
template<typename T>
typename btree_t<T>::node_iterator_t&
btree_t<T>::get_lca_node_iterator(int leaf_x, int leaf_y)
{
  //int lca = get_lca( leaf_internal_idx(leaf_x), leaf_internal_idx(leaf_y) );
  // tree_message( "has lca: " << lca << " of x=" << leaf_internal_idx(leaf_x) << " y=" << leaf_internal_idx(leaf_y) );
  int lca = get_lca_idx( leaf_x, leaf_y );
  return node_iterator_map[lca];
}

template<typename T>
typename btree_t<T>::node_iterator_t&
btree_t<T>::get_nth_node_iterator(int n)
{
#ifdef DEBUG
  assert( n >= 0 && n < ((int)ntot) );
#endif

  return node_iterator_map[n];
}


// leaf node data
template<typename T>
typename btree_t<T>::node_iterator_t&
btree_t<T>::get_leaf_node_iterator(int leaf)
{
  return node_iterator_map[leaf_internal_idx(leaf)];
}

#endif /* BTREE_HH_ */
